package Leetcode100Hot;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []

提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
 */
public class _56组合总和 {

    @Test
    public void test() {
        combinationSum(new int[]{2,3,5}, 8);
    }

    //回溯
    //156ms
    //ps：注意答案(本体为nums)在传递时不应该进行改变，否则在回溯时会导致不可预知的错误
    //ps: List是地址在进行传递，直接改变会导致答案进行变化，所以要List<Integer> list = new ArrayList<>();
    //ps:优化:剪枝
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Backtrack(res, list, candidates, 0, 0, target);
        return res;
    }

    /*
    public void Backtrack(List<List<Integer>> res, List<Integer> nums, int[] candidates, int sum, int target) {
        if (sum == target) {
            ArrayList<Integer> arrayList = new ArrayList<>(nums);
            Collections.sort(arrayList);
            if (!res.contains(arrayList)) {
                res.add(arrayList);
            }
            return;
        }

        for (int i = 0; i < candidates.length; i++) {
            nums.add(candidates[i]);
            if (sum + candidates[i] <= target) {
                Backtrack(res, nums, candidates, sum + candidates[i], target);
            }
            nums.remove(nums.size() - 1);
        }
    }
    */

    //优化
    //4ms
    public void Backtrack(List<List<Integer>> res, List<Integer> nums,int[] candidates,int index,int sum ,int target) {
        if (index == candidates.length){
            return;
        }
        if (sum == target) {
            ArrayList<Integer> arrayList = new ArrayList<>(nums);
            Collections.sort(arrayList);
            if (!res.contains(arrayList)) {
                res.add(arrayList);
            }
            return;
        }
        Backtrack(res, nums, candidates, index + 1, sum, target);
        if (sum + candidates[index] <= target) {
            nums.add(candidates[index]);
            Backtrack(res, nums, candidates, index, sum + candidates[index], target);
            nums.remove(nums.size() - 1);
        }
    }

    //官解：搜索回溯
    //2ms
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/combination-sum/solutions/406516/zu-he-zong-he-by-leetcode-solution/
     */
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> ans = new ArrayList<List<Integer>>();
            List<Integer> combine = new ArrayList<Integer>();
            dfs(candidates, target, ans, combine, 0);
            return ans;
        }

        public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
            if (idx == candidates.length) {
                return;
            }
            if (target == 0) {
                ans.add(new ArrayList<Integer>(combine));
                return;
            }
            // 直接跳过
            dfs(candidates, target, ans, combine, idx + 1);
            // 选择当前数
            if (target - candidates[idx] >= 0) {
                combine.add(candidates[idx]);
                dfs(candidates, target - candidates[idx], ans, combine, idx);
                combine.remove(combine.size() - 1);
            }
        }
    }

}
